home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / CompactStringArray.java < prev    next >
Text File  |  1998-09-22  |  17KB  |  451 lines
  1. /*
  2.  * @(#)CompactStringArray.java    1.9 97/10/28
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996 - All Rights Reserved
  6.  *
  7.  * Portions copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
  8.  *
  9.  *   The original version of this source code and documentation is copyrighted
  10.  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  11.  * materials are provided under terms of a License Agreement between Taligent
  12.  * and Sun. This technology is protected by multiple US and International
  13.  * patents. This notice and attribution to Taligent may not be removed.
  14.  *   Taligent is a registered trademark of Taligent, Inc.
  15.  *
  16.  * Permission to use, copy, modify, and distribute this software
  17.  * and its documentation for NON-COMMERCIAL purposes and without
  18.  * fee is hereby granted provided that this copyright notice
  19.  * appears in all copies. Please refer to the file "copyright.html"
  20.  * for further important copyright and licensing information.
  21.  *
  22.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  23.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  24.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  25.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  26.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  27.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  28.  *
  29.  */
  30.  
  31. package java.text;
  32.  
  33. /**
  34.  * class CompactATypeArray : use only on primitive data types
  35.  * Provides a compact way to store information that is indexed by Unicode
  36.  * values, such as character properties, types, keyboard values, etc.This
  37.  * is very useful when you have a block of Unicode data that contains
  38.  * significant values while the rest of the Unicode data is unused in the
  39.  * application or when you have a lot of redundance, such as where all 21,000
  40.  * Han ideographs have the same value.  However, lookup is much faster than a
  41.  * hash table.
  42.  * A compact array of any primitive data type serves two purposes:
  43.  * <UL type = round>
  44.  *     <LI>Fast access of the indexed values.
  45.  *     <LI>Smaller memory footprint.
  46.  * </UL>
  47.  * A compact array is composed of a index array and value array.  The index
  48.  * array contains the indicies of Unicode characters to the value array.
  49.  *
  50.  * @see                CompactShortArray
  51.  * @see                CompactByteArray
  52.  * @see                CompactIntArray
  53.  * @see                CompactCharArray
  54.  * @version            1.9 10/28/97
  55.  * @author             Helena Shih
  56.  */
  57. final class CompactStringArray implements Cloneable {
  58.  
  59.     /**
  60.      * The total number of Unicode characters.
  61.      */
  62.     public static  final int UNICODECOUNT =65536;
  63.  
  64.     /**
  65.      * Default constructor for CompactStringArray, the default value of the
  66.      * compact array is "".
  67.      */
  68.     public CompactStringArray()
  69.     {
  70.         this("");
  71.     }
  72.     /**
  73.      * Constructor for CompactStringArray.
  74.      * @param defaultValue the default value of the compact array.
  75.      */
  76.     public CompactStringArray(String defaultValue)
  77.     {
  78.         int i;
  79.         values = new char[UNICODECOUNT]; /*type = char*/
  80.         indices = new short[INDEXCOUNT];
  81.         setElementAt((char)0,'\uFFFF',defaultValue);
  82.         for (i = 0; i < INDEXCOUNT; ++i) {
  83.             indices[i] = (short)(i<<BLOCKSHIFT);
  84.         }
  85.         isCompact = false;
  86.     }
  87.     /**
  88.      * Constructor for CompactStringArray.
  89.      * @param indexArray the indicies of the compact array.
  90.      * @param newValues the values of the compact array.
  91.      * @exception IllegalArgumentException If the index is out of range.
  92.      */
  93.     public CompactStringArray(short indexArray[],
  94.                               char[] newValues,
  95.                               String exceptions)
  96.     {
  97.         int i;
  98.         if (indexArray.length != INDEXCOUNT)
  99.             throw new IllegalArgumentException("Index out of bounds.");
  100.         for (i = 0; i < INDEXCOUNT; ++i) {
  101.             short index = indexArray[i];
  102.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  103.                 throw new IllegalArgumentException("Index out of bounds.");
  104.         }
  105.         indices = indexArray;
  106.         values = newValues;
  107.     }
  108.     /**
  109.      * Get the mapped value (String) of a Unicode character.
  110.      * @param index the character to get the mapped value with
  111.      * @param toAppendTo the string buffer to append the values to
  112.      */
  113.     public void elementAt(char index, StringBuffer toAppendTo)
  114.     {
  115.         char result = (values[(indices[index>>BLOCKSHIFT] & 0xFFFF) +
  116.                              (index & BLOCKMASK)]);
  117.         if (result >= '\uE000' && result <= '\uF800') {
  118.             for (int i = (int) result - 0xE000; ; ++i) {
  119.                 result = exceptions.charAt(i);
  120.                 if (result == '\uFFFF') return;
  121.                 toAppendTo.append(result);
  122.             }
  123.         } else {
  124.             toAppendTo.append(result);
  125.         }
  126.     }
  127.     /**
  128.      * Get the mapped value of a Unicode character.
  129.      * @param index the character to get the mapped value with
  130.      * @return the mapped value of the given character
  131.      */
  132.     public String elementAt(char index) {
  133.         StringBuffer result = new StringBuffer();
  134.         elementAt(index,result);
  135.         return result.toString();
  136.     }
  137.     /**
  138.      * Set a new value for a Unicode character.
  139.      * Set automatically expands the array if it is compacted.
  140.      * @param index the character to set the mapped value with
  141.      * @param value the new mapped value
  142.      */
  143.     public void setElementAt(char index, String value)
  144.     {
  145.         if (isCompact)
  146.             expand();
  147.         if (value.length() == 1) {
  148.             char ch = value.charAt(0);
  149.             if (ch < '\uE000' || ch >= '\uF800') {
  150.                 values[(int)index] = ch;
  151.                 return;
  152.             }
  153.         }
  154.         // search for the string to see if it is already present
  155.         String temp = value + '\uFFFF';
  156.         int position = exceptions.toString().indexOf(temp);
  157.         if (position != -1) {
  158.             values[(int)index] = (char)(0xE000 + position);
  159.             return;
  160.         };
  161.         // if not found, append.
  162.         values[(int)index] = (char) (0xE000 + exceptions.length());
  163.         for (int i = 0; i < value.length(); ++i) {
  164.             exceptions.append(value.charAt(i));
  165.         }
  166.         exceptions.append('\uFFFF');    // termination
  167.     }
  168.     /**
  169.      * Set new values for a range of Unicode character.
  170.      * @param start the starting offset of the range
  171.      * @param end the ending offset of the range
  172.      * @param value the new mapped value
  173.      */
  174.    public void setElementAt(char start, char end, String value)
  175.     {
  176.         if (start >= end) return; // catch degenerate case
  177.         setElementAt(start,value);
  178.         char firstValue = values[(int)start];
  179.         for (int i = start + 1; i <= end; ++i) {
  180.             values[i] = firstValue;
  181.         }
  182.     }
  183.     /**
  184.      * Compact the array.
  185.      */
  186.     public void compact()
  187.     {
  188.         if (isCompact == false) {
  189.             char[]      tempIndex;
  190.             int                     tempIndexCount;
  191.             char[]          tempArray;
  192.             short           iBlock, iIndex;
  193.  
  194.             // make temp storage, larger than we need
  195.             tempIndex = new char[UNICODECOUNT];
  196.             // set up first block.
  197.             tempIndexCount = BLOCKCOUNT;
  198.             for (iIndex = 0; iIndex < BLOCKCOUNT; ++iIndex) {
  199.                 tempIndex[iIndex] = (char)iIndex;
  200.             }; // endfor (iIndex = 0; .....)
  201.             indices[0] = (short)0;
  202.  
  203.             // for each successive block, find out its first position
  204.             // in the compacted array
  205.             for (iBlock = 1; iBlock < INDEXCOUNT; ++iBlock) {
  206.                 int     newCount, firstPosition, block;
  207.                 block = iBlock<<BLOCKSHIFT;
  208.                 if (DEBUGSMALL) if (block > DEBUGSMALLLIMIT) break;
  209.                 firstPosition = FindOverlappingPosition(block, tempIndex,
  210.                                                         tempIndexCount);
  211.  
  212.                 newCount = firstPosition + BLOCKCOUNT;
  213.                 if (newCount > tempIndexCount) {
  214.                     for (iIndex = (short)tempIndexCount;
  215.                          iIndex < newCount;
  216.                          ++iIndex) {
  217.                         tempIndex[iIndex]
  218.                             = (char)(iIndex - firstPosition + block);
  219.                     } // endfor (iIndex = tempIndexCount....)
  220.                     tempIndexCount = newCount;
  221.                 } // endif (newCount > tempIndexCount)
  222.                 indices[iBlock] = (short)firstPosition;
  223.             } // endfor (iBlock = 1.....)
  224.  
  225.             // now allocate and copy the items into the array
  226.             tempArray = new char[tempIndexCount];
  227.             for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
  228.                 tempArray[iIndex] = values[tempIndex[iIndex]];
  229.             }
  230.             values = null;
  231.             values = tempArray;
  232.             isCompact = true;
  233.         } // endif (isCompact != false)
  234.     }
  235.     /** For internal use only.  Do not modify the result, the behavior of
  236.      * modified results are undefined.
  237.      */
  238.     public short getIndexArray()[]
  239.     {
  240.         return indices;
  241.     }
  242.     /** For internal use only.  Do not modify the result, the behavior of
  243.       * modified results are undefined.
  244.       */
  245.     public char getStringArray()[]
  246.     {
  247.         return values;
  248.     }
  249.     /**
  250.      * Overrides Cloneable
  251.      */
  252.     public Object clone()
  253.     {
  254.         try {
  255.             CompactStringArray other = (CompactStringArray) super.clone();
  256.             other.values = (char[])values.clone();
  257.             other.indices = (short[])indices.clone();
  258.             other.exceptions = new StringBuffer(exceptions.toString());
  259.             return other;
  260.         } catch (CloneNotSupportedException e) {
  261.             throw new InternalError();
  262.         }
  263.     }
  264.     /**
  265.      * Compares the equality of two compact array objects.
  266.      * @param obj the compact array object to be compared with this.
  267.      * @return true if the current compact array object is the same
  268.      * as the compact array object obj; false otherwise.
  269.      */
  270.     public boolean equals(Object obj) {
  271.         if (obj == null) return false;
  272.         if (this == obj)                      // quick check
  273.             return true;
  274.         if (getClass() != obj.getClass())         // same class?
  275.             return false;
  276.         CompactStringArray other = (CompactStringArray) obj;
  277.         for (int i = 0; i < UNICODECOUNT; i++) {
  278.             // could be sped up later
  279.             if (elementAt((char)i) != other.elementAt((char)i))
  280.                 return false;
  281.         }
  282.         return true; // we made it through the guantlet.
  283.     }
  284.     /**
  285.      * Generates the hash code for the compact array object
  286.      */
  287.  
  288.     public int hashCode() {
  289.         int result = 0;
  290.         int increment = Math.min(3, values.length/16);
  291.         for (int i = 0; i < values.length; i+= increment) {
  292.             result = result * 37 + values[i];
  293.         }
  294.         return result;
  295.     }
  296.     /**
  297.       * package private : for internal use only
  298.       */
  299.     void writeArrays()
  300.     {
  301.         int i;
  302.         int cnt = 0;
  303.         if (values.length > 0)
  304.             cnt = values.length;
  305.         else
  306.             cnt = values.length + UNICODECOUNT;
  307.         System.out.println("{");
  308.         for (i = 0; i < INDEXCOUNT-1; i++)
  309.         {
  310.             System.out.print("(short)" + (int)((getIndexArrayValue(i) >= 0) ?
  311.                 (int)getIndexArrayValue(i) :
  312.                 (int)(getIndexArrayValue(i)+UNICODECOUNT)) + ", ");
  313.             if (i != 0)
  314.                 if (i % 10 == 0)
  315.                     System.out.println();
  316.         }
  317.         System.out.println("(char)" +
  318.                            (int)((getIndexArrayValue(INDEXCOUNT-1) >= 0) ?
  319.                            (int)getIndexArrayValue(i) :
  320.                            (int)(getIndexArrayValue(i)+UNICODECOUNT)) + " }");
  321.         System.out.println("{");
  322.         for (i = 0; i < cnt-1; i++)
  323.         {
  324.             char ch = getArrayValue(i);
  325.             if (ch < 0x20 || (ch > 0x7E && ch < 0xA0) || ch > 0x100)
  326.                 System.out.print("(char)0x" +
  327.                     Integer.toString((int)ch,16).toUpperCase() + ",");
  328.             else System.out.print("\'" + ch + "\',");
  329.             if (i != 0)
  330.                 if (i % 10 == 0)
  331.                     System.out.println();
  332.         }
  333.         System.out.println("(char)" + (int)getArrayValue(cnt-1) + " }");
  334.         System.out.println("\"" + exceptions.toString() + "\"");
  335.     }
  336.     // Print char Array  : Debug only
  337.     void printIndex(char start, short count)
  338.     {
  339.         int i;
  340.         for (i = start; i < count; ++i)
  341.         {
  342.             System.out.println(i + " -> : " +
  343.                                (int)((indices[i] >= 0) ?
  344.                                      indices[i] : indices[i] + UNICODECOUNT));
  345.         }
  346.         System.out.println();
  347.     }
  348.     void printPlainArray(int start,int count, char[] tempIndex)
  349.     {
  350.         int iIndex;
  351.         if (tempIndex != null)
  352.         {
  353.             for (iIndex     = start; iIndex < start + count; ++iIndex)
  354.             {
  355.                 System.out.print(" " + (int)getArrayValue(tempIndex[iIndex]));
  356.             }
  357.         }
  358.         else
  359.         {
  360.             for (iIndex = start; iIndex < start + count; ++iIndex)
  361.             {
  362.                 System.out.print(" " + (int)getArrayValue(iIndex));
  363.             }
  364.         }
  365.         System.out.println("    Range: start " + start + " , count " + count);
  366.     }
  367.     /**
  368.      * private functions
  369.      */
  370.     /**
  371.       * Expanded takes the array back to a 65536 element array
  372.       */
  373.     private void expand()
  374.     {
  375.         int i;
  376.         if (isCompact) {
  377.             char[]  tempArray;
  378.             tempArray = new char[UNICODECOUNT];
  379.             for (i = 0; i < UNICODECOUNT; ++i) {
  380.                 tempArray[i] =(values[((int)indices[i>>BLOCKSHIFT] & 0xFFFF) +
  381.                                      (i & BLOCKMASK)]);;
  382.             }
  383.             for (i = 0; i < INDEXCOUNT; ++i) {
  384.                 indices[i] = (short)(i<<BLOCKSHIFT);
  385.             }
  386.             values = null;
  387.             values = tempArray;
  388.             isCompact = false;
  389.         }
  390.     }
  391.     // # of elements in the indexed array
  392.     private short capacity()
  393.     {
  394.         return (short)values.length;
  395.     }
  396.     private char getArrayValue(int n)
  397.     {
  398.         return values[n];
  399.     }
  400.     private short getIndexArrayValue(int n)
  401.     {
  402.         return indices[n];
  403.     }
  404.     private int
  405.     FindOverlappingPosition(int start, char[] tempIndex, int tempIndexCount)
  406.     {
  407.         int i;
  408.         short j;
  409.         short currentCount;
  410.  
  411.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  412.             printPlainArray(start, BLOCKCOUNT, null);
  413.             printPlainArray(0, tempIndexCount, tempIndex);
  414.         }
  415.         for (i = 0; i < tempIndexCount; i += BLOCKCOUNT) {
  416.             currentCount = (short)BLOCKCOUNT;
  417.             if (i + BLOCKCOUNT > tempIndexCount) {
  418.                 currentCount = (short)(tempIndexCount - i);
  419.             }
  420.             for (j = 0; j < currentCount; ++j) {
  421.                 if (values[start + j] != values[tempIndex[i + j]]) break;
  422.             }
  423.             if (j == currentCount) break;
  424.         }
  425.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  426.             for (j = 1; j < i; ++j) {
  427.                 System.out.print(" ");
  428.             }
  429.             printPlainArray(start, BLOCKCOUNT, null);
  430.             System.out.println("    Found At: " + i);
  431.         }
  432.         return i;
  433.     }
  434.  
  435.     private static  final int DEBUGSHOWOVERLAPLIMIT = 100;
  436.     private static  final boolean DEBUGTRACE = false;
  437.     private static  final boolean DEBUGSMALL = false;
  438.     private static  final boolean DEBUGOVERLAP = false;
  439.     private static  final int DEBUGSMALLLIMIT = 30000;
  440.     private static  final int BLOCKSHIFT =7;
  441.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  442.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  443.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  444.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  445.  
  446.     private char[] values;  // char -> short (char parameterized short)
  447.     private short indices[];
  448.     private StringBuffer exceptions = new StringBuffer();
  449.     private boolean isCompact;
  450. };
  451.